[백준 알고리즘] 1789번: 수들의 합
April 07, 2021
https://www.acmicpc.net/problem/1789
문제
문제
서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?
입력
첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.
출력
첫째 줄에 자연수 N의 최댓값을 출력한다.
풀이
그냥 수학적으로 푸는 방법도 있지만, 이분탐색을 연습하기 위해서 이분탐색으로 풀었다. N을 찾을 때 N개의 서로 다른 수로 S를 만들 수 있는지 확인하려면, 1부터 N-1 까지의 값을 모두 더하고, 이 값이 N 보다 큰 값인지 확인해보면 된다. 만약 N 보다 작은 값이 나오면 이미 1부터 N-1 까지 더하면서 사용한 값이기 때문에 중복되는 수를 사용해야 S를 만들 수 있다는 것을 의미한다.
코드
#include <iostream>
using namespace std;
long long calcSum(long long N) {
long long sum = 0;
for (long long i = 0; i < N; i++) {
sum += i;
}
return sum;
}
long long binarySearch(long long target) {
long long head = 1;
long long tail = target;
long long answer = 0;
while (head <= tail) {
long long mid = (head + tail) / 2;
long long sum = calcSum(mid);
if (target - sum >= mid) {
answer = mid;
head = mid + 1;
}
else {
tail = mid - 1;
}
}
return answer;
}
int main() {
long long S;
cin >> S;
cout << binarySearch(S);
}
